public class IowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left == null ? right : left;



//        HashMap<TreeNode, TreeNode> father = new HashMap<>();
//        father.put(root, root);
//        process(root, father);
//        HashSet<TreeNode> set = new HashSet<>();
//        TreeNode temp = p;
//        while (p != father.get(p)) {
//            set.add(p);
//            p = father.get(p);
//        }
//        set.add(root);
//        temp = q;
//        while (temp != father.get(temp)) {
//            if (!set.add(temp)) {
//                return temp;
//            } else {
//                temp = father.get(temp);
//            }
//        }
//        return root;
    }

//    public void process(TreeNode node, HashMap<TreeNode, TreeNode> father) {
//        if (node == null) return;
//        father.put(node.left, node);
//        father.put(node.right, node);
//        process(node.left, father);
//        process(node.right, father);
//    }
}
